home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1996 / MacHack 1996.toast / Presentations / Presentations ’96 / Papers ’96 / Book of Practical Objects / BasicObjects ƒ / BoyerMoore.cp < prev    next >
Encoding:
Text File  |  1996-05-17  |  4.1 KB  |  211 lines  |  [TEXT/CWIE]
  1. #include "BoyerMoore.h"
  2. #include <string.h>
  3. #include <ctype.h>
  4.  
  5.     BoyerMoore::BoyerMoore(void)
  6. {
  7.     fStringLen = 0;
  8.     fSearchDataLen = 0;
  9.     fStartingOffset = 0;
  10.     fSearchDataVoid = nil;
  11.     fSearchData = nil;
  12. }
  13.  
  14.  
  15.     BoyerMoore::BoyerMoore(char* searchStr, short searchLen, void* searchData, long searchDataLen)
  16. {
  17.     SetSearchString(searchStr, searchLen);
  18.  
  19.     fStartingOffset = 0;
  20.     fSearchData = nil;
  21.     
  22.     if (searchData == nil)
  23.     {
  24.         fSearchDataVoid = nil;
  25.         fSearchDataLen = 0;
  26.     }
  27.     else {
  28.             fSearchDataVoid = searchData;
  29.             fSearchDataLen = searchDataLen;
  30.          }
  31.     
  32.     BuildSkipTable();
  33. }
  34.  
  35.  
  36.     BoyerMoore::~BoyerMoore(void)
  37. {
  38.  
  39. }
  40.  
  41.     
  42. void    BoyerMoore::SetSearchString(char *searchStr, short searchLen)
  43. {
  44.     memmove(fSearchString, searchStr, searchLen);
  45.     fStringLen = searchLen;
  46.     
  47.     BuildSkipTable();
  48. }
  49.  
  50.  
  51. void    BoyerMoore::SetSearchString(Str255 searchStr)
  52. {
  53.     memmove(fSearchString, &searchStr[1], searchStr[0]);
  54.     fStringLen = searchStr[0];
  55.     
  56.     BuildSkipTable();
  57. }
  58.  
  59.  
  60. void    BoyerMoore::SetSearchData(void *searchData, long dataLen)
  61. {
  62.     fSearchDataVoid = searchData;
  63.     fSearchDataLen = dataLen;
  64.     
  65.     fStartingOffset = 0;
  66. }
  67.  
  68.  
  69. #ifdef    NEVER
  70. long    BoyerMoore::Search(void)    // Assumes all parameters have been setup
  71. {
  72.     long    dataIndex;
  73.     long    dataIndexLimit;
  74.     short    searchIndex;
  75.     long    result = -1;
  76.  
  77.  
  78.     PrepareSearchData();
  79.     
  80.     dataIndexLimit = fSearchDataLen - fStartingOffset;
  81.     for (dataIndex = 0; dataIndex < dataIndexLimit; dataIndex++)
  82.     {
  83.         if (dataIndex < fStringLen)        // We could still match
  84.         {
  85.             for (searchIndex = fStringLen - 1; searchIndex <= 0; searchIndex--)
  86.             {
  87.                 if (fSearchData[dataIndex] != fSeachString[searchIndex])    // Jump ahead
  88.                 {
  89.                     dataIndex += fSkipTable[fSearchString[searchIndex]]; 
  90.                 }
  91.                 else    // Characters matched, let us try the next character
  92.                     
  93.             }
  94.         }
  95.         else            // Not enough data to make a full match
  96.             break;        // Leave the dataIndex loop with result == -1
  97.  
  98.     }
  99. }
  100. #endif
  101.  
  102.  
  103. long    BoyerMoore::Search(void)    // Assumes all parameters have been setup
  104. {
  105.     long    dataIndex;
  106.     long    dataIndexLimit;
  107.     short    searchIndex;
  108.     long    result = -1;
  109.     Boolean    matchFail;
  110.  
  111.     PrepareSearchData();
  112.     
  113.     int    i, j, t, M, N;
  114.     
  115.     M = fStringLen;
  116.     N = fSearchDataLen - fStartingOffset;
  117.  
  118.     for (i = M-1, j = M-1; j> 0; i--, j--)
  119.     {
  120.         do
  121.         {
  122.             if (fCaseInsensitive)
  123.                 matchFail = tolower(fSearchString[j]) != tolower(fSearchData[i]);
  124.             else
  125.                 matchFail = fSearchString[j] != fSearchData[i];
  126.             // fSearchString[j] != fSearchData[i])
  127.             if (matchFail)        // If they didn't match
  128.             {
  129.                 t = fSkipTable[fSearchData[i]];        // Skip some characters
  130.                 i += (M-j > t) ? M-j : t;
  131.                 if (i >= N)                            // If we can't match in remaining length
  132.                     return (result);                // return the failure value
  133.                 j = M-1;
  134.             }
  135.         }
  136.         while (matchFail);
  137.     }
  138.     result = i;
  139.     
  140.     CleanupSearchData();
  141.     return (result);
  142. }
  143.  
  144.  
  145. long    BoyerMoore::Search(long startingOffset, char *searchStr, short searchLen)    // Where we want to start searching
  146. {
  147.     long    result;
  148.  
  149.     if (searchStr != nil)
  150.         SetSearchString(searchStr, searchLen);
  151.     
  152.     fStartingOffset = startingOffset;
  153.     
  154.     result = Search();
  155.     return (result);
  156. }
  157.  
  158.  
  159. long    BoyerMoore::Search(long startingOffset, Str255 searchStr)
  160. {
  161.     long    result;
  162.  
  163.     fStartingOffset = startingOffset;
  164.     if (searchStr != nil)
  165.         SetSearchString(searchStr);
  166.     
  167.     result = Search();
  168.     return (result);
  169. }
  170.  
  171.  
  172. // If you passed in a Handle for fSearchDataVoid, then you could override this
  173. // method and lock the handle before starting the search (although this doesn't
  174. // move memory and you shouldn't need to.
  175. void    BoyerMoore::PrepareSearchData(void)    // Setup the interall data for searching
  176. {
  177.     fSearchData = ((unsigned char*)fSearchDataVoid) + fStartingOffset;
  178. }
  179.  
  180.  
  181. void    BoyerMoore::CleanupSearchData(void)    // Let it go if it was locked or marked
  182. {
  183.     // You could unlock the handle here if you wanted
  184. }
  185.  
  186. void    BoyerMoore::BuildSkipTable(void)
  187. {
  188.     short    i;
  189.     short    skipLen;
  190.     short    index;
  191.     
  192.     
  193.     for (i = 0; i < 255; i++)        // Initialize the table with basic jump values
  194.     {
  195.         fSkipTable[i] = fStringLen;
  196.     }
  197.     
  198.     // now walk through the search string to
  199.     // figure out how far we can slide the string if we failed
  200.     // to match the last character
  201.     for (i = 0; i < fStringLen; i++)
  202.     {
  203.         skipLen = fStringLen - i - 1;
  204.         index = fSearchString[i];
  205.         fSkipTable[index] = skipLen;
  206.     }
  207.     
  208. }
  209.  
  210.  
  211.